package cn.xie.wrench;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;

/**
 * @author: xiaoxie
 * create: 2025-05-13 21:01
 * @BelongsProject: qiuzhaoshuati
 * @BelongsPackage: cn.xie.wrench
 * description: 牛客101
 */
public class Niuke {
    /**
     * @description: 牛客必刷101 双指针
     * BM88 判断是否为回文字符串
     * <a href="https://www.nowcoder.com/practice/e297fdd8e9f543059b0b5f05f3a7f3b2?tpId=295&tqId=1089616&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间 O(n) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/15 下午3:32
     * @param: [str]
     * @return: boolean
     **/
    public boolean judge(String str) {
        // write code here
        int left = 0;
        int right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public class Interval {
        int start;
        int end;

        public Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    /**
     * @description: 牛客必刷101 双指针
     * BM89 合并区间
     * <a href="https://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a?tpId=295&tqId=691&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间 O(N),空间 O(1)
     * @author: xiaoxie
     * @date: '2025/5/15' 下午8:57
     * @param: [intervals]
     * @return: java.util.ArrayList<cn.xie.wrench.Niuke.Interval>
     **/
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        /**
         这题有点综合的味道了,使用排序加贪心
         先将所有的 interval 按照 start的顺序开始排序
         之后先把第一个interval 放到 ans数组中 记 res
         之后在比较后续的interval 记 next
         if res.end < next.start
         ans.add(next)
         else  合并
         ans.remove(res);
         if(res.end < next.end)
         new res.start,next.end
         res.start,res.end;
         */
        if (intervals.isEmpty()) {
            return new ArrayList<>();
        }
        intervals.sort(new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if (o1.start != o2.start)
                    return o1.start - o2.start;
                else
                    return o1.end - o2.end;
            }
        });
        ArrayList<Interval> ans = new ArrayList<>();
        ans.add(intervals.get(0));
        for (int i = 1; i < intervals.size(); i++) {
            Interval res = ans.get(ans.size() - 1);
            Interval next = intervals.get(i);
            if (res.end < next.start) {
                ans.add(next);
            } else {
                res.end = Math.max(res.end, next.end);
            }
        }
        return ans;
    }

    /**
     * @description: 牛客必刷101 双指针
     * BM91 反转字符串
     * <a href="https://www.nowcoder.com/practice/c3a6afee325e472386a1c4eb1ef987f3?tpId=295&tqId=1024337&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page&dayCountBigMember=365%E5%A4%A9">...</a>
     * 时间 O(N),空间 O(N)
     * @author: xiaoxie
     * @date: 2025/5/15 下午9:27
     * @param: [str]
     * @return: java.lang.String
     **/
    public String solve(String str) {
        char[] cstr = str.toCharArray();
        int len = str.length();
        for (int i = 0; i < len / 2; i++) {
            char t = cstr[i];
            cstr[i] = cstr[len - 1 - i];
            cstr[len - 1 - i] = t;
        }
        return new String(cstr);
    }

    /**
     * @description: 牛客必刷101 双指针
     * BM92 最长无重复子数组
     * <a href="https://www.nowcoder.com/practice/b56799ebfd684fb394bd315e89324fb4?tpId=295&tqId=1008889&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间 O(N),空间 O(N)
     * @author: xiaoxie
     * @date: 2025/5/16 下午11:53
     * @param: [arr]
     * @return: int
     **/
    public int maxLength(int[] arr) {
        HashMap<Integer, Integer> hash = new HashMap<>();
        int ans = 0, left = 0;
        for (int right = 0; right < arr.length; right++) {
            hash.put(arr[right], hash.getOrDefault(arr[right], 0) + 1);
            while (hash.get(arr[right]) > 1) {
                hash.put(arr[left], hash.get(arr[left]) - 1);
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }

    /**
     * @description: 牛客必刷101 双指针
     * BM93 盛水最多的容器
     * <a href="https://www.nowcoder.com/practice/3d8d6a8e516e4633a2244d2934e5aa47?tpId=295&tqId=2284579&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间 O(N),空间 O(1)
     * @author: xiaoxie
     * @date: 2025/5/17 上午12:01
     * @param: [height]
     * @return: int
     **/
    public int maxArea(int[] height) {
        /**
         使用相向双指针
         */
        int n = height.length;
        int left = 0, right = n - 1, ans = 0;
        while (left < right) {
            int s = (right - left) * (Math.min(height[left], height[right]));
            ans = Math.max(s, ans);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return ans;
    }

    /**
     * @description: 牛客101 二分查找类型
     * BM17 二分查找-I
     * <a href="https://www.nowcoder.com/practice/d3df40bd23594118b57554129cadf47b?tpId=295&tqId=1499549&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间 O(LogN) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/2 下午10:06
     * @param: [nums, target]
     * @return: int
     **/
    public int search(int[] nums, int target) {
        int left = -1;
        int right = nums.length;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        if (right == nums.length || nums[right] != target) {
            return -1;
        }
        return right;
    }

    /**
     * @description: 牛客101 二分查找类型
     * BM19 寻找峰值
     * <a href="https://www.nowcoder.com/practice/fcf87540c4f347bcb4cf720b5b350c76?tpId=295&tqId=2227748&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间 O(LogN) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/2 下午10:10
     * @param: [nums]
     * @return: int
     **/
    public int findPeakElement(int[] nums) {
        int left = -1;
        int right = nums.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1]) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return right;
    }

    /**
     * @description: 牛客101 二分查找类型
     * BM21 旋转数组的最小数字
     * <a href="https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=295&tqId=23269&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间 O(LogN) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/2 下午10:19
     * @param: [nums]
     * @return: int
     **/
    public int minNumberInRotateArray(int[] nums) {
        int left = -1;
        int right = nums.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid;
            } else if (nums[mid] == nums[right]) {
                right--;
            } else {
                right = mid;
            }
        }
        return nums[right];
    }

    public class ListNode {
        int val;
        ListNode next = null;

        public ListNode(int val) {
            this.val = val;
        }
    }

    /**
     * @description: 牛客101 链表类型
     * BM1 反转链表
     * <a href="https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=295&tqId=23286&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/11 下午8:40
     * @param: [head]
     * @return: cn.xie.wrench.Niuke.ListNode
     **/
    public ListNode ReverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * @description: 牛客101 链表类型
     * BM2 链表内指定区间反转
     * <a href="https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/11 下午9:11
     * @param: [head, m, n]
     * @return: cn.xie.wrench.Niuke.ListNode
     **/
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(1);
        dummy.next = head;
        ListNode p = dummy;
        for (int i = 1; i < m; i++) {
            p = p.next;
        }
        ListNode cur = p.next;
        ListNode pre = null;
        for (int i = 0; i < n - m + 1; i++) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        p.next.next = cur;
        p.next = pre;
        return dummy.next;
    }

    /**
     * @description: 牛客101 链表类型
     * BM3 链表中的节点每k个一组翻转
     * <a href="https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/11 下午9:16
     * @param: [head, k]
     * @return: cn.xie.wrench.Niuke.ListNode
     **/
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode p = dummy;
        ListNode cur = head;
        int n = 0;
        while (cur != null) {
            cur = cur.next;
            n++;
        }
        cur = head;
        ListNode pre = null;
        while (n >= k) {
            n -= k;
            for (int i = 0; i < k; i++) {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            ListNode pNext = p.next;
            p.next.next = cur;
            p.next = pre;
            p = pNext;
        }
        return dummy.next;
    }

    /**
     * @description: 牛客101 链表类型
     * BM4 合并两个排序的链表
     * <a href="https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=295&tqId=23267&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/11 下午9:22
     * @param: [pHead1, pHead2]
     * @return: cn.xie.wrench.Niuke.ListNode
     **/
    public ListNode Merge(ListNode pHead1, ListNode pHead2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (pHead1 != null && pHead2 != null) {
            if (pHead1.val <= pHead2.val) {
                cur = cur.next = new ListNode(pHead1.val);
                pHead1 = pHead1.next;
            } else {
                cur = cur.next = new ListNode(pHead2.val);
                pHead2 = pHead2.next;
            }
        }
        cur.next = pHead1 == null ? pHead2 : pHead1;
        return dummy.next;
    }

    /**
     * @description: 牛客101 链表类型
     * BM5 合并k个已排序的链表
     * <a href="https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间复杂度：O(Llogm)，其中 m 为 lists 的长度，L 为所有链表的长度之和。每个节点参与链表合并的次数为 O(logm) 次，一共有 L 个节点，所以总的时间复杂度为 O(Llogm)。
     * 空间复杂度：O(logm)。递归深度为 O(logm)，需要 O(logm) 的栈空间。Python 忽略切片产生的额外空间。
     * @author: xiaoxie
     * @date: 2025/6/11 下午9:36
     * @param: [lists]
     * @return: cn.xie.wrench.Niuke.ListNode
     **/
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        return sortLists(lists, 0, lists.size() - 1);
    }

    private ListNode sortLists(ArrayList<ListNode> lists, int left, int right) {
        if (left > right) return null;
        if (left == right) return lists.get(left);
        int mid = left + (right - left) / 2;
        ListNode l1 = sortLists(lists, left, mid);
        ListNode l2 = sortLists(lists, mid + 1, right);
        return marge(l1, l2);
    }

    private ListNode marge(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur = cur.next = new ListNode(l1.val);
                l1 = l1.next;
            } else {
                cur = cur.next = new ListNode(l2.val);
                l2 = l2.next;
            }
        }
        cur.next = l1 == null ? l2 : l1;
        return dummy.next;
    }

    /**
     * @description: 牛客101 链表类型
     * BM6 判断链表中是否有环
     * <a href="https://www.nowcoder.com/practice/650474f313294468a4ded3ce0f7898b9?tpId=295&tqId=605&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/11 下午9:40
     * @param: [head]
     * @return: boolean
     **/
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) return true;
        }
        return false;
    }

    /**
     * @description: 牛客101 链表类型
     * BM7 链表中环的入口结点
     * <a href="https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/11 下午9:53
     * @param: [head]
     * @return: cn.xie.wrench.Niuke.ListNode
     **/
    public ListNode EntryNodeOfLoop(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                ListNode cur = head;
                while (cur != slow) {
                    cur = cur.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
    /**
     * @description: 牛客101 链表类型
     * BM8 链表中倒数最后k个结点
     * <a href="https://www.nowcoder.com/practice/886370fe658f41b498d40fb34ae76ff9?tpId=295&tqId=1377477&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/11 下午10:07
     * @param: [head, k]
     * @return: cn.xie.wrench.Niuke.ListNode
     **/
    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = head;
        for (int i = 0; i < k; i++) {
            if (fast.next != null) {
                fast = fast.next;
            } else {
                return slow = null;
            }
        }

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
    /**
     * @description: 牛客101 链表类型
     * BM9 删除链表的倒数第n个节点
     * <a href="https://www.nowcoder.com/practice/f95dcdafbde44b22a6d741baf71653f6?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/11 下午10:10
     * @param: [head, n]
     * @return: cn.xie.wrench.Niuke.ListNode
     **/
    public ListNode removeNthFromEnd (ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        for(int i = 0;i < n;i++) {
            fast = fast.next;
        }
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
    /**
     * @description: 牛客101 链表类型
     * BM10 两个链表的第一个公共结点
     * <a href="https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/11 下午10:33
     * @param: [head1, head2]
     * @return: cn.xie.wrench.Niuke.ListNode
     **/
    public ListNode FindFirstCommonNode(ListNode head1, ListNode head2) {
        // l1 (x + c) + y = l2 (y + c) + x;
        ListNode l1 = head1;
        ListNode l2 = head2;
        while(l1 != null || l2 != null) {
            if(l1 == l2) {
                return l1;
            }
            l1 = l1 != null ? l1.next : head2;
            l2 = l2 != null ? l2.next : head1;
        }
        return null;
    }
    /**
     * @description: 牛客101 链表类型
     * BM11 链表相加(二)
     * <a href="https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b?tpId=295&tqId=1008772&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间 O(N) 空间 O(1)
     * @author: xiaoxie
     * @date: 2025/6/11 下午10:40
     * @param: [head1, head2]
     * @return: cn.xie.wrench.Niuke.ListNode
     **/
    public ListNode addInList (ListNode head1, ListNode head2) {
        ListNode l1 = reverse(head1);
        ListNode l2 = reverse(head2);
        int curry = 0;
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while(l1 != null || l2 != null || curry != 0) {
            int a = l1 == null ? 0 : l1.val;
            curry += a;
            int b = l2 == null ? 0 : l2.val;
            curry += b;
            cur = cur.next = new ListNode(curry % 10);
            l1 = l1 != null ? l1.next : null;
            l2 = l2 != null ? l2.next : null;
            curry /= 10;
        }

        return reverse(dummy.next);
    }
    private ListNode reverse(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    /**
     * @description: 牛客101 链表类型
     * BM12 单链表的排序
     * <a href="https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08?tpId=295&tqId=1008897&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间O(nlog2n) 空间(log2n)
     * @author: xiaoxie
     * @date: 2025/6/11 下午10:52
     * @param: [head]
     * @return: cn.xie.wrench.Niuke.ListNode
     **/
    public ListNode sortInList (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode mid = search(head);
        ListNode l1 = sortInList(head);
        ListNode l2 = sortInList(mid);
        return marge1(l1, l2);
    }
    private ListNode search(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = head;
        while (fast != null && fast.next != null) {
            pre = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        pre.next = null;
        return slow;
    }
    private ListNode marge1(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur = cur.next = new ListNode(l1.val);
                l1 = l1.next;
            } else {
                cur = cur.next = new ListNode(l2.val);
                l2 = l2.next;
            }
        }
        cur.next = l1 == null ? l2 : l1;
        return dummy.next;
    }
    /**
     * @description: 牛客101 链表类型
     * BM13 判断一个链表是否为回文结构
     * <a href="https://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f?tpId=295&tqId=1008769&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间O(n) 空间(1)
     * @author: xiaoxie
     * @date: 2025/6/11 下午10:56
     * @param: [head]
     * @return: boolean
     **/
    public boolean isPail (ListNode head) {
        ListNode head2 = reverse1(searchMid(head));
        while(head2 != null) {
            if(head2.val != head.val) {
                return false;
            }
            head2 = head2.next;
            head = head.next;
        }
        return true;
    }
    private ListNode searchMid(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    private ListNode reverse1(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    /**
     * @description: 牛客101 链表类型
     * BM14 链表的奇偶重排
     * <a href="https://www.nowcoder.com/practice/02bf49ea45cd486daa031614f9bd6fc3?tpId=295&tqId=1073463&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间O(n) 空间(1)
     * @author: xiaoxie
     * @date: 2025/6/11 下午11:07
     * @param: [head]
     * @return: cn.xie.wrench.Niuke.ListNode
     **/
    public ListNode oddEvenList (ListNode head) {
        if(head == null) {
            return head;
        }
        ListNode j = head;
        ListNode o = head.next;
        ListNode oHead = head.next;
        while(o != null && o.next != null) {
            j.next = o.next;
            j = j.next;
            o.next = j.next;
            o = o.next;
        }
        j.next = oHead;
        return head;
    }
    /**
     * @description: 牛客101 链表类型
     * BM15 删除有序链表中重复的元素-I
     * <a href="https://www.nowcoder.com/practice/c087914fae584da886a0091e877f2c79?tpId=295&tqId=664&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间O(n) 空间(1)
     * @author: xiaoxie
     * @date: 2025/6/11 下午11:15
     * @param: [head]
     * @return: cn.xie.wrench.Niuke.ListNode
     **/
    public ListNode deleteDuplicates (ListNode head) {
        if(head == null) {
            return head;
        }
        ListNode cur = head;
        while(cur.next != null) {
            int v = cur.val;
            if(cur.next.val == v) {
                while(cur.next != null && cur.next.val == v) {
                    cur.next = cur.next.next;
                }
            }else {
                cur = cur.next;
            }

        }
        return head;
    }
    /**
     * @description: 牛客101 链表类型
     * BM16 删除有序链表中重复的元素-II
     * <a href="https://www.nowcoder.com/practice/71cef9f8b5564579bf7ed93fbe0b2024?tpId=295&tqId=663&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page">...</a>
     * 时间O(n) 空间(1)
     * @author: xiaoxie
     * @date: 2025/6/11 下午11:21
     * @param: [head]
     * @return: cn.xie.wrench.Niuke.ListNode
     **/
    public ListNode deleteDuplicates2 (ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;
        while(cur.next != null && cur.next.next != null) {
            int v = cur.next.val;
            if(cur.next.next.val == v) {
                while(cur.next != null && cur.next.val == v) {
                    cur.next = cur.next.next;
                }
            }else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}
